\section{Решетки}

Решетка: частично-упорядоченное множество $(L,\sqsubseteq)$, для которого выполнено 
следующее свойство: для произвольных $x, y\in L$ определены следующие значения:

$$
x\sqcap y=\max\:\{t\mid t\sqsubseteq x \;\mbox{и}\; t\sqsubseteq y\}
$$

$$
x\sqcup y=\min\:\{t\mid t\sqsupseteq x \;\mbox{и}\; t\sqsupseteq y\}
$$

Далее будем считать, что приоритеты ``$\sqcap$'' и ``$\sqcup$'' равны и выше, чем приоритет
``$\sqsubseteq$''.

Свойства:

\begin{enumerate}
\item $x\sqsubseteq y$ тогда и только тогда, когда $x\sqcap y=x$ (очевидно);
\item $x\sqcap y=y\sqcap x$ (очевидно);
\item $x\sqcap y\sqsubseteq x$ (очевидно);
\item Если $z\sqsubseteq x$, то для любого $x$ $z\sqcap y\sqsubseteq x$ (очевидно).
\item Если $x\sqsubseteq y$, то для любого $z$ 

$$
x\sqcap z \sqsubseteq y\sqcap z
$$

Действительно:

$$
x\sqcap z=\max\:\{t\mid t\sqsubseteq x\;\mbox{и}\;t\sqsubseteq z\}
$$
$$
y\sqcap z=\max\:\{t\mid t\sqsubseteq y\;\mbox{и}\;t\sqsubseteq z\}
$$

Но поскольку $x\sqsubseteq y$, имеем

$$
\{t\mid t\sqsubseteq x\;\mbox{и}\;t\sqsubseteq z\}\subseteq\{t\mid t\sqsubseteq y\;\mbox{и}\;t\sqsubseteq z\}
$$

и, следовательно,

$$
\max\:\{t\mid t\sqsubseteq x\;\mbox{и}\;t\sqsubseteq z\}\sqsubseteq\max\:\{t\mid t\sqsubseteq y\;\mbox{и}\;t\sqsubseteq z\}
$$

\item Неравенства можно почленно пересекать:

$$
\begin{array}{c}
x\sqsubseteq y\\
z\sqsubseteq t\\ 
\hline
x\sqcap z\sqsubseteq y\sqcap t
\end{array}
$$

Действительно:

$$
x\sqcap z=\max\;\{p\mid p\sqsubseteq x\;\mbox{и}\;p\sqsubseteq z\}
$$
$$
y\sqcap t=\max\;\{p\mid p\sqsubseteq y\;\mbox{и}\;p\sqsubseteq t\}
$$

Но так как $x\sqsubseteq y$ и $z\sqsubseteq t$, имеем

$$
\{p\mid p\sqsubseteq x\;\mbox{и}\;p\sqsubseteq z\}\subseteq\{p\mid p\sqsubseteq y\;\mbox{и}\;p\sqsubseteq t\}
$$

откуда

$$
\max\:\{p\mid p\sqsubseteq x\;\mbox{и}\;p\sqsubseteq z\}\sqsubseteq\max\:\{p\mid p\sqsubseteq y\;\mbox{и}\;p\sqsubseteq t\}
$$

\item Из предыдущего следует, что почленно пересекать можно и равенства.

\item Пересечение дистрибутивно: $(x\sqcap y)\sqcap z=(x\sqcap z)\sqcap(y\sqcap z)$.
Действительно, 

$$
\begin{array}{c}
x\sqsupseteq x\sqcap z\\
y\sqsupseteq y\sqcap z\\
\hline
x\sqcap y\sqsupseteq (x\sqcap z)\sqcap(y\sqcap z)
\end{array}
$$

Пересечем в полученном неравенстве обе части с $z$ (это можно сделать по свойству 5):

$$
(x\sqcap y)\sqcap z\sqsupseteq ((x\sqcap z)\sqcap(y\sqcap z))\sqcap z
$$

Но так как $(x\sqcap z)\sqcap(y\sqcap z)$, очевидно, меньше $z$, правая часть этого
неравенства есть просто $(x\sqcap z)\sqcap(y\sqcap z)$. Таким образом, получаем

$$
(x\sqcap y)\sqcap z\sqsupseteq (x\sqcap z)\sqcap(y\sqcap z)
$$

Теперь докажем противоположное неравенство:

\begin{tabular}{p{3cm}p{3cm}}
$$
\begin{array}{c}
(x\sqcap y)\sqcap z\sqsubseteq x\\
(x\sqcap y)\sqcap z\sqsubseteq z\\
\hline
(x\sqcap y)\sqcap z\sqsubseteq x\sqcap z
\end{array}
$$ &
$$
\begin{array}{c}
(x\sqcap y)\sqcap z\sqsubseteq y\\
(x\sqcap y)\sqcap z\sqsubseteq z\\
\hline
(x\sqcap y)\sqcap z\sqsubseteq y\sqcap z
\end{array}
$$
\end{tabular}

Почленное пересечение полученных неравенств и дает искомое:

$$
(x\sqcap y)\sqcap z\sqsubseteq (x\sqcap z)\sqcap (y\sqcap z)
$$

\item Пересечение ассоциативно. Действительно, 

$$
(x\sqcap y)\sqcap z\stackrel{\mbox{\tiny{дистрибутивность}}}{=}(x\sqcap z)\sqcap(y\sqcap z)=(x\sqcap(y\sqcap z))\sqcap(z\sqcap(y\sqcap z))
$$

Учитывая, что $y\sqcap z\sqsubseteq z$, получаем $z\sqcap(y\sqcap z)=y\sqcap z$. Аналогично,
из $x\sqcap(y\sqcap z)\sqsubseteq y\sqcap z$ следует $(x\sqcap(y\sqcap z))\sqcap(y\sqcap z)=x\sqcap(y\sqcap z)$

\end{enumerate}

Полные решетки (где существуют пересечения и объединения произвольных семейств элементов). Пересечение всех = объединение пустого = 
наименьший элемент, объединение всех = пересечение пустого = наибольший элемент.

Далее:

\begin{enumerate}
\item Пусть есть два семейства $\{x_i\}$ и $\{y_i\}$, причем $\forall i\;x_i\sqsubseteq y_i$. Тогда

$$\bigsqcap x_i\sqsubseteq\bigsqcap y_i$$

Действительно, $\forall i\; x_i\sqcap y_i=x_i$. Тогда $(\bigsqcap x_i)\sqcap(\bigsqcap y_i)=\bigsqcap(x_i\sqcap y_i)=\bigsqcap x_i$.
Следовательно, $\bigsqcap x_i\sqsubseteq\bigsqcap y_i$.

\item Пусть есть $\{x_i\}$ и $y$, такие, что $\forall i\; y\sqsubseteq x_i$. Тогда $y\sqsubseteq \bigsqcap x_i$. Действительно, так как $x_i\sqcap y\sqsubseteq x_i$, 
то $\bigsqcap x_i \sqsupseteq \bigsqcap (x_i\sqcap y) = \bigsqcap y = y$.
\end{enumerate}

Монотонные функции. Свойства (для полных решеток): $f(\bigsqcup x_i)\sqsupseteq\bigsqcup f(x_i)$, $f(\bigsqcap x_i)\sqsubseteq\bigsqcap f(x_i)$ для произвольного
(не обязательно счётного) семейства $\{x_i\}$.

Теорема Тарского-Кнастера. Пусть $(L, \sqsubseteq)$ --- полная решетка, $f$ --- монотонная функция. Тогда:

\begin{enumerate}
\item $\gfp{f}=\bigsqcup\{x\mid f(x)\sqsupseteq x\}$ --- наибольшая неподвижная точка $f$;
\item $\lfp{f}=\bigsqcap\{x\mid f(x)\sqsubseteq x\}$ --- наименьшая неподвижная точка $f$;
\item $\{x\mid f(x)=x\}$ --- полная подрешетка $L$.
\end{enumerate}

Доказательство: во-первых, $\{x \mid f(x)\sqsupseteq x\}$ переводится $f$ в свое ``верхнее подмножество''. Во-вторых,
$f(\bigsqcup\{x\mid f(x)\sqsupseteq x\})\sqsupseteq\bigsqcup\{f(x)\mid f(x)\sqsupseteq x\}$ по монотонности $f$.
Но то, что справа, это просто $\{x \mid f(x)\sqsupseteq x\}$ (по во-первых). Стало быть,
$\bigsqcup\{x\mid f(x)\sqsupseteq x\}\in \{x\mid f(x)\sqsupseteq x\}$ и (опять по во-первых)
$f(\bigsqcup\{x\mid f(x)\sqsupseteq x\})\in \{x\mid f(x)\sqsupseteq x\}$. Но, конечно, объединение
разве что больше каждого члена --- следовательно, $f(\bigsqcup\{x\mid f(x)\sqsupseteq x\})\sqsubseteq\bigsqcup\{x\mid f(x)\sqsupseteq x\}$ ---
получили оба неравенства; следовательно, $\bigsqcup\{x\mid f(x)\sqsupseteq x\}$ --- неподвижная точка $f$.

Почему она наибольшая? Потому, что любая другая неподвижная точка принадлежит $\{x\mid f(x)\sqsupseteq x\}$, и поэтому 
разве что меньше объединения.

Аналогично доказывается, что $\lfp{f}$ --- наименьшая неподвижная точка.

Полнота: пусть $P$ --- нек. подмножество неп. точек $f$. У него есть объединение в $L$. Но
$f(\bigsqcup P)\sqsupseteq P$ (по монотонности $f$ и потому, что $P$ --- мно-во неподв. точек). Но тогда
$f$ --- монотонная ф-я в полной подрешетке $[\bigsqcup P,\top_L]$. Стало быть, у нее есть наименьшая
неподв. точка --- она и будет ниаменьшей верхней гранью $P$.


